package middle;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution_229 {

    public static void main(String[] args) {
        Solution_229 model = new Solution_229();
        System.out.println(model.majorityElement(new int[]{3,2,3}));
        System.out.println(model.majorityElement(new int[]{1}));
        System.out.println(model.majorityElement(new int[]{1, 2}));
        System.out.println(model.majorityElement(new int[]{4, 2, 1, 1}));
    }

    /**
     * 空闲阵营的数量
     */
    private int freeArenaNum;
    /**
     * 阵营集合
     */
    private List<Arena> arenas;
    /**
     * 阵营编码和阵营对象的映射
     */
    private Map<Integer, Arena> arenaValMap;

    public List<Integer> majorityElement(int[] nums) {
        initArena(3);
        for (int i = 0; i < nums.length; i++) {
            if (arenaValMap.containsKey(nums[i])) {
                // 存在阵营，直接加入
                arenaValMap.get(nums[i]).nums++;
                arenaValMap.get(nums[i]).historyNums++;
            } else {
                Arena freeArena = findFreeArena();
                freeArena.val = nums[i];
                freeArena.nums = 1;
                freeArena.historyNums = 1;
                arenaValMap.put(nums[i], freeArena);
                freeArenaNum--;
            }
            kill();
        }

        int limit = nums.length / 3;
        List<Integer> list = new ArrayList<>(arenas.size() - freeArenaNum);
        for (Arena arena : arenaValMap.values()) {
            int count = 0;
            for (int num : nums) {
                if (num == arena.val) {
                    count++;
                }
            }
            if (count > limit) {
                list.add(arena.val);
            }
        }
        return list;
    }

    /**
     * 初始化阵营对象
     * @param num 阵营数量
     */
    private void initArena(int num) {
        freeArenaNum = num;
        arenaValMap = new HashMap<>();
        arenas = new ArrayList<>(num);
        for (int i = 0; i < num; i++) {
            arenas.add(new Arena());
        }
    }

    /**
     * 寻找空闲阵营
     * @return
     */
    private Arena findFreeArena() {
        for (Arena arena : arenas) {
            if (arena.nums == 0) {
                return arena;
            }
        }
        return null;
    }

    /**
     * 开始厮杀
     */
    private void kill() {
        if (freeArenaNum > 0) {
            return;
        }
        int killNum = Integer.MAX_VALUE;
        for (Arena arena : arenas) {
            if (arena.nums < killNum) {
                killNum = arena.nums;
            }
        }
        if (killNum <= 0) {
            return;
        }
        for (Arena arena : arenas) {
            arena.nums -= killNum;
            if (arena.nums==0) {
                freeArenaNum++;
                arenaValMap.remove(arena.val);
            }
        }
    }

    /**
     * 擂台
     */
    static class Arena {

        /**
         * 阵营编码
         */
        public int val;

        /**
         * 阵营人数
         */
        public int nums = 0;

        /**
         * 历史总人数
         */
        public int historyNums = 0;
    }
}
